package tree;

import java.util.ArrayList;
import java.util.List;
import java.util.TreeMap;

public class _113_路径总和_II {


    /**
     * 给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
     * <p>
     * 说明: 叶子节点是指没有子节点的节点。
     *
     * @param root
     * @param targetSum
     * @return
     */
    public static List<List<Integer>> pathSum1(TreeNode root, int targetSum){
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        List<Integer> path = new ArrayList<>();
        dfs1(root, result, path, targetSum);
        return result;
    }

    private static void dfs1(TreeNode root, List<List<Integer>> result, List<Integer> path, int targetSum) {
        if (root == null) {
            return;
        }
        int val = root.val;
        path.add(val);
        if (targetSum-val == 0 && root.left==null && root.right == null) {
            result.add(new ArrayList<>(path));
            return;
        }
        dfs1(root.left, result, path, targetSum - val);
        if (root.left!=null) {
            path.remove(path.size()-1);
        }
        dfs1(root.right, result, path, targetSum - val);
        if (root.right != null) {
            path.remove(path.size() -1);
        }
    }

    public static List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> result = new ArrayList<>();

        if (root == null) {
            return result;
        }

        dfs(new ArrayList<>(), result, root, targetSum);
        return result;
    }

    private static void dfs(List<Integer> cur, List<List<Integer>> result,
                     TreeNode root, int targetSum) {
        if (root == null) {
            return;
        }

        int val = root.val;
        int i = targetSum - val;
        cur.add(val);
        if (i == 0 && root.left == null && root.right == null) {
            result.add(new ArrayList<>(cur));
            return;
        }
        dfs(cur, result, root.left, i);
        if (!cur.isEmpty()&& root.left!=null) {
            cur.remove(cur.size() - 1);
        }
        dfs(cur, result, root.right, i);
        if (!cur.isEmpty()&& root.right!=null) {
            cur.remove(cur.size() - 1);
        }
    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(5);
        TreeNode treeNode1 = new TreeNode(4);
        TreeNode treeNode2 = new TreeNode(8);
        TreeNode treeNode3 = new TreeNode(11);
        TreeNode treeNode4 = new TreeNode(13);
        TreeNode treeNode5 = new TreeNode(4);
        TreeNode treeNode6 = new TreeNode(7);
        TreeNode treeNode7 = new TreeNode(2);
        TreeNode treeNode8 = new TreeNode(5);
        TreeNode treeNode9 = new TreeNode(1);
        treeNode.left = treeNode1;
        treeNode.right = treeNode2;
        treeNode1.left = treeNode3;
        treeNode2.left = treeNode4;
        treeNode2.right = treeNode5;
        treeNode3.left = treeNode6;
        treeNode3.right = treeNode7;
        treeNode5.left = treeNode8;
        treeNode5.right = treeNode9;
        List<List<Integer>> lists = pathSum1(treeNode, 22);


    }
}
